#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
    return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
    return pf.write(pid, buffer);
}

/* Note:
 *  each BTLeafNode contains:
 *  ||rid|key|rid|key|....|pid||
 *
 *  PageFile::PAGE_SIZE = 1024
 *  the size of each entry: sizeof(rid) + sizeof(key)    
 *  so the maximum number of pair is (1024 - sizeof(pid))/ sizeof(rid) + sizeof(key)
 * Two constant variables are declared: LEAF_ENTRY_SIZE and LEAF_MAX_ENTRY
 */

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
    int* bptr = (int*) buffer; //buffer pointer
    int count = 0;    
    
    for(int index = 0; index < LEAF_MAX_ENTRY; index = index+LEAF_ENTRY_SIZE){
        RecordId rid;
        int key;
        rid.pid = *(bptr + index);
        rid.sid = *(bptr + index + sizeof(PageId));
        key = *(bptr + index + sizeof(PageId) + sizeof(int));
        
        // empty record
        if(key == -1 && rid.pid == -1 && rid.sid == -1){
            break;
        }
        else{
            count++;
        }
    }
    
    return count;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
    int current_key_count = getKeyCount();
    if(current_key_count >= LEAF_MAX_ENTRY){
        return RC_NODE_FULL;
    }

    int eid;
    char* tempbuffer = buffer;

    // shuffle the records
    if(locate(key, eid) > 0){
        for(int e_index = current_key_count; e_index > eid; e_index--){
            memcpy(tempbuffer+e_index*LEAF_ENTRY_SIZE, tempbuffer+(e_index-1)*LEAF_ENTRY_SIZE, LEAF_ENTRY_SIZE);
        }

    }
    // insert to the last position, no record shuffling required
    else{
        eid = current_key_count;
    }
    
    memcpy(tempbuffer+(eid * LEAF_ENTRY_SIZE), &rid, sizeof(RecordId));
    memcpy(tempbuffer+(eid * LEAF_ENTRY_SIZE)+sizeof(RecordId), &key, sizeof(int));
        
    return 0;

}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
    int eid;
    char *tmpbuffer = buffer;
    PageId siblingPid = -1;
    int total_size = getKeyCount();
    int half_point = total_size /2 ;
    int split_point = total_size / 2;    
    RC status;
    
    // locate the insertion point
    if(!locate(key, eid)){
        eid = LEAF_ENTRY_SIZE;
    }

    // odds number of entry, if the new key is inserted after the split point 
    if(total_size % 2 != 0 && eid > half_point){
        split_point = split_point + 1;
    }
    
    // move all the second half to the sibling node
    for(int i = split_point; i < total_size; i++){
        RecordId rid2;
        int key2;
        memcpy(&rid2,tmpbuffer + i*LEAF_ENTRY_SIZE,sizeof(RecordId));
        memcpy(&key2, tmpbuffer + i*LEAF_ENTRY_SIZE + sizeof(RecordId), sizeof(int));
        sibling.insert(key2, rid2);
        if(siblingPid == -1){
            siblingPid = rid2.pid;
            siblingKey = key2;
        }
        
        // clear the original buffer after moving
        int clearkey = -1;
        RecordId clearRid = {-1,-1};
        memcpy(tmpbuffer + i * LEAF_ENTRY_SIZE, &clearRid, sizeof(RecordId));
        memcpy(tmpbuffer + i * LEAF_ENTRY_SIZE + sizeof(RecordId), &clearkey, sizeof(int));
    
    }
    
    // insert the key    
    if(eid <= half_point){  //insert into first half
        status = insert(key, rid);
    }
    else{  // insert into second half
        status = sibling.insert(key, rid);

        if(eid == half_point){ // update sibling key if the insert value became the first item in sibling node
            siblingKey = key;
            siblingPid = rid.pid;
        }
    }

    // if the inserts are okay, update PageId
    if(status == 0){
        sibling.setNextNodePtr(getNextNodePtr());
        setNextNodePtr(siblingPid);
        return 0;
    }
    else{
        return status;
    }
    
    
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 	int numKeys = getKeyCount();
	int key;
	char *tempbuffer = buffer; // pointer to element 0 of buffer
	
	for (int i = 0; i < numKeys; i++)
	{
		memcpy(&key, tempbuffer, sizeof(int));
		tempbuffer += (LEAF_ENTRY_SIZE); // go to next entry
		if (key >= searchKey)
		{
			eid = i;
			return 0;
		}	
	}
	
	return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	if (eid < 0 || eid >= getKeyCount())
	{
		return RC_INVALID_CURSOR;
	}
    
	char *tempbuffer = buffer;
	tempbuffer += eid*(LEAF_ENTRY_SIZE);
	memcpy(&rid, tempbuffer, sizeof(RecordId));
    tempbuffer += sizeof(RecordId);
    memcpy(&key, tempbuffer, sizeof(int));
    
    return 0;
    
}
/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	PageId pid;
	char *tempbuffer = buffer;
    //	int numKeys = getKeyCount();
    //	tempbuffer += (numKeys*(LEAF_ENTRY_SIZE));
	tempbuffer += (PageFile::PAGE_SIZE - sizeof(PageId));
	memcpy(&pid, tempbuffer, sizeof(PageId));
	return pid;
}


// allocate memeory
void BTLeafNode::initialize()
{
    int key = -1;
    RecordId rid = {-1,-1};
    for(int i = 0; i < LEAF_MAX_ENTRY; i++){
        char buf[LEAF_ENTRY_SIZE];
        memcpy(buf, &rid, sizeof(RecordId));
        memcpy(buf+sizeof(RecordId), &key, sizeof(int));
        memcpy(buffer + i*LEAF_ENTRY_SIZE, buf, LEAF_ENTRY_SIZE);
    }
    setNextNodePtr(-1);
    
}



/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
    char *tempbuffer = buffer;
    //  int numKeys = getKeyCount();
    //  tempbuffer += (numKeys*(LEAF_ENTRY_SIZE));
	tempbuffer += (PageFile::PAGE_SIZE - sizeof(PageId));
    memcpy(tempbuffer, &pid, sizeof(PageId));
    return 0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
    return pf.read(pid, buffer);
                   
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
    return pf.write(pid, buffer);

}


/* Note:
 *  each BTNonLeafNode contains:
 *  ||pid|key|pid|key|....|pid||
 *
 *  PageFile::PAGE_SIZE = 1024
 *  the size of each entry: sizeof(pid) + sizeof(key)    
 *  so the maximum number of pair is (1024 - sizeof(pid))/ sizeof(pid) + sizeof(key)
 * Two constant variables are declared: NONLEAF_ENTRY_SIZE and NONLEAF_MAX_ENTRY
 */


/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
    int count = 0;
    char* tmpbuffer = buffer;

    for(int i = 0; i < NONLEAF_MAX_ENTRY; i++){
        PageId pid;
        int key;
        
        memcpy(&pid, tmpbuffer+(i*NONLEAF_ENTRY_SIZE), sizeof(PageId));
        memcpy(&key, tmpbuffer+(i*NONLEAF_ENTRY_SIZE) + sizeof(PageId), sizeof(int));
        
        if(pid == -1 && key == -1){
            break;
        }
        count++;
        
    }
    return count;

}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
    
    int current_key_count = getKeyCount();
    if(current_key_count >= NONLEAF_MAX_ENTRY){
        return RC_NODE_FULL;
    }
    
    char* tempbuffer = buffer;
    
    // shuffle the records that contain a key which is larger than input key
    for(int index = getKeyCount(); index > 0; index++){
        int exist_key;
        memcpy(&exist_key, tempbuffer+(index-1)*NONLEAF_ENTRY_SIZE,sizeof(int));
        
        // if the exisiting key is larger than input, shufflt this entry
        if(exist_key > key){
            memcpy(tempbuffer+index*NONLEAF_ENTRY_SIZE, tempbuffer+(index-1)*NONLEAF_ENTRY_SIZE, NONLEAF_ENTRY_SIZE);
        }
        
        // if the input key is larger than exisiting key, insert the key, and exist the loop
        else{
            memcpy(tempbuffer+index*NONLEAF_ENTRY_SIZE, &pid, sizeof(PageId));
            memcpy(tempbuffer+index*NONLEAF_ENTRY_SIZE+sizeof(PageId), &key, sizeof(int));
            return 0;
        }
        
    }
    
    // insert to the first entry
    memcpy(tempbuffer, &key, sizeof(int)); 
    memcpy(tempbuffer+sizeof(int), &pid, sizeof(PageId));
    
    return 0;

}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{

    char *tmpbuffer = buffer;
    int total_size = getKeyCount() + 1;
    int half_point = total_size / 2;
    int insertion_point = -1;
    RC status = 0;
    int clearkey = -1;
    PageId clearPid = -1;
    
    // find out the insertion position for key
    for(int i = 0; i < getKeyCount(); i++){
        int current_key;
        memcpy(&current_key, tmpbuffer+i*NONLEAF_ENTRY_SIZE+sizeof(PageId), sizeof(int));
        if(current_key > key){
            insertion_point = i;
            break;
        }        
    }
    if(insertion_point == -1){  // if all of the keys are smaller than inserted key, put in the last position
        insertion_point = getKeyCount();
    }
    
    // return and remove the midKey
    if(insertion_point == half_point){
        midKey = key;
        insertion_point = -1; // no need to insert this element to current or sibling node
        half_point --;
    }
    else if(insertion_point < half_point){
        half_point --;  // midKey would be one element before the midpoint
        midKey = *(buffer+half_point*NONLEAF_ENTRY_SIZE+sizeof(PageId));
        memcpy(tmpbuffer + half_point*NONLEAF_ENTRY_SIZE + sizeof(PageId), &clearkey, sizeof(int));
    }
    else{
        midKey = *(buffer+half_point*NONLEAF_ENTRY_SIZE+sizeof(PageId));
        memcpy(tmpbuffer + half_point*NONLEAF_ENTRY_SIZE + sizeof(PageId), &clearkey, sizeof(int));
    }
    
    // move elements
    for(int i = half_point + 1; i < getKeyCount(); i++){
        PageId pid2;
        int key2;
        memcpy(&pid2, tmpbuffer+ i*NONLEAF_ENTRY_SIZE, sizeof(PageId));
        memcpy(&key2, tmpbuffer+ i*NONLEAF_ENTRY_SIZE + sizeof(PageId), sizeof(int));
        sibling.insert(key2, pid2);
        
        // clear the original buffer after moving
        memcpy(tmpbuffer + i * NONLEAF_ENTRY_SIZE, &clearPid, sizeof(PageId));
        memcpy(tmpbuffer + i * NONLEAF_ENTRY_SIZE + sizeof(PageId), &clearkey, sizeof(int));
    }
    
    // insert element
    if(insertion_point > half_point){
        status = insert(key, pid);
    }
    else if(insertion_point != -1){
        status = sibling.insert(key, pid);
    }

    return status;
    
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	// pageid | key | pageid | key | pageid | ... | pageid non-leaf pointer
	char *tempbuffer = buffer;
	int keylooker; // looks at key
	int numKeys = getKeyCount(); // # of pageid == # of key + 1
	
	for (int i = 0; i < numKeys; i++)
	{
		memcpy(&keylooker, tempbuffer+sizeof(PageId), sizeof(int));
		
		if (searchKey < keylooker)
		{
			memcpy(&pid, tempbuffer, sizeof(PageId));
			return 0;
		}
		else if (searchKey == keylooker)
		{
			memcpy(&pid, tempbuffer+sizeof(PageId)+sizeof(int), sizeof(PageId));
			return 0;
		}
		else
		{
			tempbuffer += (sizeof(PageId) + sizeof(int));
		}
	}
	
	return RC_NO_SUCH_RECORD;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	char *tempbuffer = buffer;
	memcpy(tempbuffer, &pid1, sizeof(PageId));
	tempbuffer += sizeof(PageId);
	memcpy(tempbuffer, &key, sizeof(int));
	tempbuffer += sizeof(int);
	memcpy(tempbuffer, &pid2, sizeof(PageId));
	return 0;
}

